package org.example.algorithm.stack;

import java.util.ArrayDeque;
import java.util.Deque;

public class LargestRectangleAreaSolution {

    //分别计算出以height[i]为高度的最大值
    public int largestRectangleArea(int[] heights) {
        int len = heights.length;
        int[] left = new int[len];
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i=0;i<len;i++) {
            while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {
                stack.pop();
            }
            left[i] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(i);
        }
        int[] right = new int[len];
        stack.clear();
        for (int i=len-1;i>=0;i--) {
            while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {
                stack.pop();
            }
            right[i] = stack.isEmpty() ? len : stack.peek();
            stack.push(i);
        }
        int ans = 0;
        for (int i=0;i<len;i++) {
            ans = Math.max(ans, heights[i] * (right[i] - left[i] - 1));
        }
        return ans;
    }
}
